package com.xuliugen.lsm.util;

import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.xuliugen.lsm.core.MemTable;
import com.xuliugen.lsm.core.SSTable;
import com.xuliugen.lsm.tree.BTree;
import com.xuliugen.lsm.tree.BTreeNode;
import com.xuliugen.lsm.tree.Entry;
import com.xuliugen.lsm.tree.RBTreeNode;

public class TreeUtil {

    /**
     * 将红黑树转换成B树
     * @param rbTree
     * @param bTree
     * @return
     */
    public static <K extends Comparable<K>, V> SSTable<K, V> RBTreeToBTree(MemTable<K, V> memTable, int M) {
        SSTable<K, V> table = new SSTable<>(M);
        rbTreeToBTree(memTable.getRBtree().getRoot(), table.getBTree());
        return table;
    }

    private static <K extends Comparable<K>, V> void rbTreeToBTree(RBTreeNode<K, V> root, BTree<K, V> bTree) {
        if (root != null) {
            bTree.insert(root.getKey(), root.getValue());
            rbTreeToBTree(root.getLeft(), bTree);
            rbTreeToBTree(root.getRight(), bTree);
        }
    }

    /**
     * 合并两颗B树
     * @param ss
     * @param st
     * @param deleted
     * @return
     */
    public static <K extends Comparable<K>, V> SSTable<K, V>
    memgerTwoBtree(SSTable<K, V> ss, SSTable<K, V> st,
                   Map<? extends Comparable<?>, Integer> deleted) {
        SSTable<K, V> newBTree = new SSTable<K, V>(st.getM());
        memgerTwoBtree(newBTree, ss.getBTree().getRoot(), deleted);
        memgerTwoBtree(newBTree, st.getBTree().getRoot(), deleted);
        return newBTree;
    }

    private static <K extends Comparable<K>, V> void memgerTwoBtree(SSTable<K, V> newBTree, BTreeNode<K, V> root,
                                                                    Map<? extends Comparable<?>, Integer> deleted) {
        if (root != null) {
            List<Entry<K, V>> entrys = root.getEntries();
            for (Entry<K, V> entry : entrys) {
                if (!deleted.containsKey(entry.getKey())) {
                    newBTree.put(entry.getKey(), entry.getValue());
                }
            }
            List<BTreeNode<K, V>> children = root.getChildren();
            for (BTreeNode<K, V> child : children) {
                memgerTwoBtree(newBTree, child, deleted);
            }
        }
    }

    /**
     * 从SStable查找元素
     * @param key
     * @param sstable
     * @return
     */
    public static <K extends Comparable<K>, V> V findKeyFromSStable(K key, Vector<K, V> sstable) {
        if (sstable != null && sstable.size() > 0) {

            for (int i = 0; i < sstable.size(); i++) {
                SSTable<K, V> s = sstable.get(i);
                V res = s.get(key);
                if (res != null) {
                    return res;
                }
            }
        }
        return null;
    }

    /**
     * 将delLog日志刷新到sstable
     * @param sstable
     * @param delLog
     */
    public static <K extends Comparable<K>, V> void delByDelLog(Vector<K, V> sstable, Map<K, Integer> delLog) {
        for (int i = 0; i < sstable.size(); i++) {
            SSTable<K, V> stable = sstable.get(i);
            Set<K> keySet = new HashSet<K>(delLog.keySet());
            for (K key : keySet) {
                stable.delete(key);
                // delLog.remove(key);
            }
        }
    }
}
